Association Rule Mining (ARM) in large transactional databases is a central problem in the field of knowledge discovery. ARM is described, for example, by Agrawal et al., in “Mining Association Rules Between Sets of Items in Large Databases,” Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., June 1993, pages 207-216, which is incorporated herein by reference.
A variety of algorithms have been developed for ARM. Such algorithms are described, for example, by Agrawal and Srikant in “Fast Algorithms for Mining Association Rules,” Proceedings of the 20th International Conference on Very Large Databases (VLDB94), Santiago, Chile, 1994, pages 487-499, which is incorporated herein by reference.
In Distributed Association Rule Mining (D-ARM), the ARM problem is restated in the context of distributed computing. Several D-ARM methods are known in the art. An exemplary D-ARM algorithm is described by Agrawal and Shafer in “Parallel Mining of Association Rules,” IEEE Transactions on Knowledge and Data Engineering (8:6), 1996, pages 962-969, which is incorporated herein by reference.
An algorithm that aims to reduce the communication load associated with D-ARM is described by Cheung et al. in “A Fast Distributed Algorithm for Mining Association Rules,” Proceedings of the 1996 International Conference on Parallel and Distributed Information Systems, Miami Beach, Fla., 1996, pages 31-44, which is incorporated herein by reference.
Schuster and Wolff describe yet another algorithm that reduces the communication overhead of the D-ARM process in “Communication-Efficient Distributed Mining of Association Rules,” Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, Santa Barbara, Calif., May 2001, pages 473-484, which is incorporated herein by reference.